package com.cjy.linkedList;

import com.sun.xml.internal.ws.api.message.Header;

import java.util.Stack;

/**
 * @Author cjy
 * @Date 2022/6/26 22:50
 * @Version 1.0
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        // 测试
        // 1.创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
        // 2.创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        // 3.将节点加入链表 ——这里有bug如果重复添加一个节点的时候，会死循环
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero4);
//        singleLinkedList.add(hero2);
//        singleLinkedList.add(hero3);

        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero2);

        //测试删除 第一个、最后一个节点
        singleLinkedList.del(4);
        // 显示链表
        singleLinkedList.showList();


    }

    /**
     * 逆序打印 单链表
     */
    public static void reversePrint(HeroNode head){
        if (head.next == null){
            // 空链表无法打印
            return;
        }
        // 使用数据结构 stack栈，栈数据结构 先进后出 的特点 实现逆序打印
        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = head.next;
        // 将链表的所有节点压入栈
        while(cur !=null){
            //出入栈
            stack.push(cur);
            //指针后移指向下一个节点
            cur =cur.next;
        }
        //将栈中的节点进行打印，即数据出栈
        while (stack.size()>0){
            System.out.println(stack.pop());
        }
    }

    /**
     *  获取单链表节点的个数（该链表有头节点）
     */
    public static int getLength(HeroNode head){
        if (head.next == null){
            return 0;
        }
        int length =0;
        HeroNode cur = head.next;
        while (cur != null){
            length ++ ;
            // 拥有下一个节点就继续遍历
            cur = cur.next;
        }
        return length;
    }

    /**
     * 【需求】：将倒数的第？个节点
     * @param head
     * @param index
     * @return
     */
    public static HeroNode findLastIndexNode(HeroNode head,int index){
        // 非空判断
        if (head.next == null){
            return null; //没有找到该节点
        }
        // 获取整个链表的长度
        int size=getLength(head);
        // 校验是否，查找的最后一个节点是否符合规范
        if (index <=0|| index>size){
            return null;
        }
        // 遍历
        // 定义一个起始指针，指针的位置就是节点对象中的next属性，
        // 🐳为什么是头节点的next?因为头节点的no为0，然后next属性就代表了当前第一个值的位置
        HeroNode cur = head.next;
        // 获取倒数的内容
        // 🐳理解难点：怎么找到该需要的节点的，是通过节点中next属性来查找的
        // 为什么要使用size-index因为链表中指针需要移动的次数，这样指针就找到倒数的节点
        for (int i =0; i<size-index; i++){
            cur =cur.next;
        }
        return cur;
    }

    /**
     * [不太懂]单链表的反转，它的实现思路是相当于创建多一个容器，来装载，即一共使用到了两个链表
     */
    public static void reversList(HeroNode head){
        // 非空判断并只有一个节点的时候不需要反转
        if(head.next == null || head.next.next ==null ){
            return;
        }
        // 定义一个指针（节点对象）。
        HeroNode cur = head.next;
        // 容器，在遍历的时候连接原链表上的节点，避免原链表上的头节点丢失
        HeroNode next = null;
        // 创建一个新链表的头节点，反转后链表的头节点，并初始化
        HeroNode reversHead = new HeroNode(0,"","");
        // [难点]
        while (cur != null){
            //因为链表其实一个对象中包含另一个对象，对象只要被调用就不会被GC回收
            next =cur.next;
            cur.next = reversHead.next;
            reversHead.next =cur;
            cur = next;
        }
        // 最后将输入的head.next头节点指 向 反转reverseHead 实现反转
        head.next =reversHead.next;
    }

}

/**
 * 1.定义一个HeroNode节点
 */
class HeroNode{
    public int no;
    public String name;
    public String nickName;
    public HeroNode next ; //指向下一个节点

    //构造器
    public HeroNode(int hNo,String hName,String hNickname){
        this.no = hNo;
        this.name =hName;
        this.nickName =hNickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}
/**
 * 2.定义单向链表，管理水浒好汉
 */
class SingleLinkedList{
    // 初始化一个头节点，头节点是不存放任何具体数据的
    private HeroNode head = new HeroNode(0,"","");

    /**
     * 单向链表中添加节点[无序版]，这种添加方式是最简单的添加方式，它不实现排序能功能
     * 实现思路：
     * 1.需要先找到最后一个节点才能添加
     * 2.将最后节点的next属性指向 下一个新的节点
     */
    public void add(HeroNode heroNode){
        // 创建指针，由于头节点是不能被直接使用(如果使用了会导致无法遍历)，所以我们需新建一个节点(指针)来辅助我们，用于找到最后一个节点
        HeroNode temp =head;
        // 通过遍历找到最后一个节点,这里的实践思路是通过死循环，找到最后一个节点才会退出
        while(true){
            // 找到链表的最后一个节点,这里因为规则就是最后一个节点为null
            if (temp.next == null){
                break;
            }
            // 如果没有找到最后一个节点，就将temp指针指向下一个节点
            temp = temp.next;
        }
        temp.next =heroNode;
    }

    /**
     * 显示链表，其实就是将链表遍历出来
     */
    public void showList(){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        // 创建指针，由于头节点是不能被直接使用(如果使用了会导致无法遍历)，所以我们需新建一个节点(指针)来辅助我们，用于找到最后一个节点
        HeroNode temp =head.next;
        while (true){
            //判断指针是否指向了最后一个节点
            if (temp == null){
                break;
            }
            // 输出节点内容：这里由于已经重写了toString方法直接打印出来即可
            System.out.println(temp);
            // 指针指向下一个节点
            temp = temp.next;
        }
    }

    /**
     * 添加节点的有序版，添加节点时链表实现按顺序自动存储，并实现去重功能
     * 🐳这种方式直接在内存中就已经实现排序
     */
    public void addByOrder(HeroNode heroNode){
        // 创建指针，由于头节点是不能被直接使用(如果使用了会导致无法遍历)，所以我们需新建一个节点(指针)来辅助我们，用于找到最后一个节点
        HeroNode temp = head;
        // 创建一个标识，用来判断节点中的编号no是否存在，存在则无法添加到节点中
        boolean flag =false;

        while(true){
            // 指针指向null 代表已到最后一个节点
            if (temp.next == null){
                break;
            }
            // 通过no,找到新增节点按顺序添加的位置 ？这里有疑问
            if (temp.next.no>heroNode.no){
                break;
            }else if (temp.next.no == heroNode.no){
                flag = true; //说明编号存在
                break;
            }
            temp =temp.next; // 指针后移，变量当前链表
        }

        //判断flag的值
        if (flag){
            // 有重复编号，无法添加
            System.out.println("有重复编号，无法添加");
        }else {
            // 插入到链表中，指针temp后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }
    /**
     * 修改：
     * 编号不能修改,因为如果节点中的编号都修改了就等于添加了
     */
    public void update(HeroNode heroNode){
        //非空判断
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        // 创建指针
        HeroNode temp =head.next;
        // 通过变量找到需要修改的节点
        // 创建标识，表示是否找到该节点
        boolean flag = false;
        while (true){
            if (temp == null){
                break; //链表已遍历完,不存在该节点
            }
            if (temp.no == heroNode.no){
                //找到该节点
                flag = true ;
                break;
            }
            //继续找下一个节点
            temp=temp.next;
        }
        // 通过flag标识，判断是否找到要修改的节点
        if (flag){
            temp.name = heroNode.name;
            temp.nickName = heroNode.nickName;
        }else {
            System.out.println("没有找到该节点");
        }
    }
    /**
     * 删除该节点
     * 🐳：这里一个很妙的思路就是：通过利用GC垃圾回收机制，自动对节点进行删除
     * 当通过修改节点中的next指向下下个节点，那么没有被其他指向引用的节点就会直接被Java GC垃圾回收
     * 实现思路：
     * 通过指针找到我们需要删除的前一个节点，比较temp.next.no和需要删除 no
     */
    public void del(int no){
        // 1.创建指针
        HeroNode temp =head;
        // 创建flag标识，标识已找到对应节点
        boolean flag =false;
        while (true){
            if (temp.next == null){
                break;
            }
            // 找到待删除的前一个节点
            if (temp.next.no== no){
                flag =true;
                break;
            }
            temp = temp.next; //temp后移。继续遍历寻找
        }
        // 通过flag标识，判断是否已找到节点
        if (flag){
            // 通过GC垃圾回收机制，会自动对未被引用的对象(节点)删除
            // 所以修改其节点对象中的next属性即可
            temp.next = temp.next.next;
        }else {
            System.out.println("不存在要删除的节点:"+ no);
        }
    }


}
